When several flows of data are passing through a network device, it may be that the rate that data is received exceeds the rate at which the data may be transmitted. As such, some of the data received must be held temporarily in queues. Queues represent memory locations where data may be held before being transmitted by the network device. Fair queuing is the name given to queuing techniques that allow each flow passing through a network device to have a fair share of network resources.
An exemplary fair queuing technique, called Deficit Round Robin (DRR) allocates bandwidth fairly among competing flows. Packets in a number of flows arriving at a network device are mapped to a number of queues. This number of queues is much less than the number of flows. A scheduler using DRR traverses the queues in a round robin manner attempting to serve a predefined quantity (a quantum) of data from each queue. Additionally, a deficit counter is associated with each queue. In each round, the scheduler increases the deficit counter of a given queue by the quantum. The deficit counter is then decreased by the amount of data served from the queue.
For example, if the quantum of a given scheduler is 1000 bytes and a queue has a 1500 byte packet to be served, the first time the queue is traversed by the given scheduler, the packet may not be served, because the packet is larger than the value (1000) in the deficit counter. In the next round, however, the packet may be served, because the packet is smaller than the value (2000) in the deficit counter. If the packet is served in the next round, the value in the deficit counter is reduced to 500.
Other known queuing techniques include Carry Over Round Robin and the classic Packetized General Processor Sharing. However, these techniques and Deficit Round Robin are recognized to show a marked increase in complexity as the number of queues served increases.